package 代码记录.校招笔试真题.笔试真题_2022.小米;

import java.net.HttpRetryException;

public class Test1 {
    /**
     *
     * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
     * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表
     * @return ac
     *
     * 当时做这道题的时候,脑袋里想的是K个一组翻转链表_25,但是最后也写出来了
     * 意味着我25题可能面试时写不出来,再看看
     */
    public ListNode<Integer> reverseBetween(ListNode<Integer> head, int left, int right) {
        ListNode<Integer> dummyHead = new ListNode<Integer>();
        dummyHead.next = head;
        ListNode temp = dummyHead;
        for(int i = 0;i < left - 1;i++){
            temp = temp.next;
        }
        ListNode prev = temp;
        ListNode start = prev.next;
        for(int i = left - 1;i < right;i++){
            temp = temp.next;
        }
        ListNode end = temp;
        ListNode list = end.next;
        end.next = null;
        prev.next = reverse(start);
        start.next = list;
        return dummyHead.next;
    }
    private ListNode<Integer> reverse(ListNode<Integer> head){
        ListNode prev = null;
        while(head != null){
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}
class ListNode<T> {
    public T data;
    public ListNode next;
}